package search;

import java.util.Arrays;

/**
 * @author yzh
 * @data 2021/3/30 20:55
 * 需要数组提前排好序
 * 时间复杂度：O(logn)
 */
public class 二分 {
    public static void main(String[] args) {
        int[] nums = {3, 1, 6, 8};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(binarySearch(nums, 0));
    }

//    static int binarySearch(int[] nums, int target) {
//        int l = 0;
//        int r = nums.length - 1;
//        while (l <= r) {
////            int mid = l + r >> 1;
//            int mid = l + ((r - l) >> 1);
//            if (nums[mid] == target) return mid;
//            if (nums[mid] < target) l = mid + 1;
//            else r = mid - 1;
//        }
//        return -1;
//    }

    static int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

}
